#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<queue>
#include<unordered_map>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
    
};

class Solution {
public:
    struct Status
    {
        int val;
        ListNode* ptr;
        bool operator<(const Status& rhs) const
        {
            return val > rhs.val;
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<Status> Q;
        for (auto node : lists)
            if (node) Q.push({ node->val,node });
        ListNode* dummy = new ListNode(-1);
        ListNode* tail = dummy;
        while (!Q.empty())
        {
            Status front = Q.top();
            Q.pop();
            tail->next = front.ptr;
            tail = tail->next;
            if (front.ptr->next)
                Q.push({ front.ptr->next->val,front.ptr->next });
        }
        return dummy->next;
    }

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode(-1);
        ListNode* tail = head;
        while (l1 && l2)
        {
            if (l1->val > l2->val)
            {
                tail->next = l2;
                l2 = l2->next;
            }
            else
            {
                tail->next = l1;
                l1 = l1->next;
            }
            tail = tail->next;
        }
        tail->next = l1 ? l1 : l2;
        return head->next;
    }

    ListNode* merge(vector<ListNode*>& lists, int l, int r)
    {
        if (l == r) return lists[l];
        if (l > r) return nullptr;
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    ListNode* _mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        int n = 0;
        ListNode* cur = head;
        while (cur)
        {
            cur = cur->next;
            ++n;
        }
        n /= k;
        cur = head;
        ListNode* newhead = new ListNode(-1);
        ListNode* prev = newhead;
        for (int i = 0; i < n; ++i)
        {
            ListNode* tmp = cur;
            for (int j = 0; j < k; ++j)
            {
                ListNode* next = cur->next;
                cur->next = prev->next;
                prev->next = cur;
                cur = next;
            }
            prev = tmp;
        }
        prev->next = cur;
        return newhead->next;
    }

    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); ++i)
        {
            if (hash.count(target - nums[i]))
                return { i,hash[target - nums[i]] };
            hash[nums[i]] = i;
        }
        return {};
    }

    bool CheckPermutation(string s1, string s2) {
        vector<int> hash1(26), hash2(26);
        for (char c : s1)
            ++hash1[c - 'a'];
        for (char c : s2)
            ++hash2[c - 'a'];
        return hash1 == hash2;
    }

    bool _CheckPermutation(string s1, string s2) {
        if (s1.size() != s2.size()) return false;
        int hash[26]{};

        for (char c : s1)
            ++hash[c - 'a'];
        for (char c : s2)
        {
            --hash[c - 'a'];
            if (hash[c - 'a'] < 0) return false;
        }
        return true;
    }

    bool containsDuplicate(vector<int>& nums) {
        unordered_map<int, int> hash;
        for (int num : nums)
        {
            if (hash[num] == 1) return true;
            ++hash[num];
        }
        return false;
    }

    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        for (int left = 0, right = 0; right < nums.size(); ++right)
        {
            ++hash[nums[right]];
            while (right - left > k && left < right)
                --hash[nums[left++]];
            if (hash[nums[right]] >= 2) return true;
        }
        return false;
    }

    bool _containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); ++i)
        {
            if (hash.count(nums[i]))
            {
                if (i - hash[nums[i]] <= k)
                    return true;
            }
            hash[nums[i]] = i;
        }
        return false;
    }

    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hash;
        for (int i = 0; i < strs.size(); ++i)
        {
            string tmp = strs[i];
            sort(tmp.begin(), tmp.end());
            hash[tmp].push_back(strs[i]);
        }
        vector<vector<string>> ans;
        for (auto v : hash)
            ans.push_back(v.second);
        return ans;
    }

    string longestCommonPrefix(vector<string>& strs) {
        string ans = strs[0];
        for (int i = 1; i < strs.size(); ++i)
        {
            int j = 0;
            while (j < min(strs[i].size(), ans.size()) && strs[i][j] == ans[j]) ++j;
            ans = ans.substr(0, j);
        }
        return ans;
    }

    string longestCommonPrefix(vector<string>& strs) {
        for (int i = 0; i < strs[0].size(); ++i)
        {
            char c = strs[0][i];
            for (int j = 1; j < strs.size(); ++j)
            {
                if (i == strs[j].size() || c != strs[j][i])
                    return strs[0].substr(0, i);
            }
        }
        return strs[0];
    }

    struct TreeNode {
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode() : val(0), left(nullptr), right(nullptr) {}
        TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
        TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}

    };

    int ans = 1;
    int dfs(TreeNode* root)
    {
        if (root == nullptr) return 0;
        int leftLen = dfs(root->left);
        int rightLen = dfs(root->right);
        ans = max(ans, leftLen + rightLen + 1);
        return max(leftLen, rightLen) + 1;
    }

    int diameterOfBinaryTree(TreeNode* root) {
        dfs(root);
        return ans - 1;
    }

    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();

        auto matches = [&](int i, int j) {
            if (i == 0)
                return false;
            if (p[j - 1] == '.')
                return true;
            return s[i - 1] == p[j - 1];
        };

        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        dp[0][0] = true;
        for (int i = 0; i <= m; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (p[j - 1] == '*')
                {
                    dp[i][j] |= dp[i][j - 2];
                    if (matches(i, j - 1))
                        dp[i][j] |= dp[i - 1][j];
                }
                else {
                    if (matches(i, j))
                        dp[i][j] |= dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }

    int jump(vector<int>& nums) {
        int maxPos = 0, end = 0, step = 0;
        for (int i = 0; i < nums.size() - 1; ++i)
        {
            maxPos = max(maxPos, i + nums[i]);
            if (i == end)
            {
                end = maxPos;
                ++step;
            }
        }
        return step;
    }
};